#include <bits/stdc++.h>
#define F(i,l,r) for(int i=(l);i<=(r);i++)
#define DF(i,l,r) for(int i=(l);i>=(r);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void read(T &x){
    x=0;int r=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') r=-1;
    for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+ch-48;
    x*=r;
}
const int N=200010,M=1000010;
const LL inf=1e18;
int n,a[N],rv[M],b[N];
struct SGT{
    LL seg[N<<2],tag[N<<2];
    void build(int l,int r,int x){
        tag[x]=0,seg[x]=-inf;
        if(l==r) return;
        int mid=(l+r)>>1;
        build(l,mid,x<<1),build(mid+1,r,x<<1^1);
    }
    void down(int x,LL v){ seg[x]+=v,tag[x]+=v;}
    void pushdown(int x){ if(tag[x]) down(x<<1,tag[x]),down(x<<1^1,tag[x]),tag[x]=0;}
    void mdf(int l,int r,int x,int pos,LL v){
        if(l==r){ chkmax(seg[x],v);return;}
        pushdown(x);
        int mid=(l+r)>>1;
        if(mid>=pos) mdf(l,mid,x<<1,pos,v);
        else mdf(mid+1,r,x<<1^1,pos,v);
        seg[x]=max(seg[x<<1],seg[x<<1^1]);
    }
    LL qry(int l,int r,int x,int pos){
        if(l==r) return seg[x];
        pushdown(x);
        int mid=(l+r)>>1;
        if(mid>=pos) return qry(l,mid,x<<1,pos);
        else return qry(mid+1,r,x<<1^1,pos);
    }
}sgt;
void work(){
    read(n);
    int mx=0;
    F(i,1,n) read(a[i]),rv[a[i]]=1,chkmax(mx,a[i]);
    int m=0;
    F(i,1,mx) if(rv[i]) rv[i]=++m,b[m]=i;
    F(i,1,n) a[i]=rv[a[i]];
    sgt.build(0,m,1),sgt.mdf(0,m,1,0,0);
    F(i,2,n){
        LL qwq=max(sgt.seg[1],sgt.qry(0,m,1,a[i])+b[a[i]]);
        if(a[i]==a[i-1]) sgt.down(1,b[a[i]]);
        sgt.mdf(0,m,1,a[i-1],qwq);
    }
    printf("%lld\n",sgt.seg[1]);
    F(i,1,mx) rv[i]=0;
}
int main(){
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    int T;read(T);
    while(T--) work();
    return 0;
}
